package test;

import sun.awt.SunHints;
import sun.plugin2.message.GetAppletMessage;

import java.security.Key;
//二叉树实现
public class BinaryTree {
    Node root;
    //添加
    public void add(int key,Object value){
        if(root==null){
            root =new Node(key,value);
            return;
        }
        Node node = new Node(key, value);

        Node node1=root;//指针初始化
        while(true){
            int test = node.key-node1.key;
            //如果test为正数则插在右子节点 负数左子节点 0则更新节点value
            if(test==0){
                node1.value=value;
                return;
            }
            if( node1.lowerRight!=null && test>0){ //如果插入节点大于指针节点同时该指针的右子节点不为空 指针向右下移动
                node1=node1.lowerRight;
                continue;
            }
            if(node1.lowerLeft!=null && test<0){//如果插入节点小于指针节点同时该指针的左子节点不为空 指针向左下移动
               node1=node1.lowerLeft;
               continue;
            }
            if(node1.lowerRight==null && test>0){
                System.out.println("插入的节点为"+key+"该节点为"+node1.key+"的右子节点");
               node1.lowerRight=node;
               return;
            }
            if(node1.lowerRight==null && test<0){
                System.out.println("插入的节点为"+key+"该节点为"+node1.key+"的左子节点");
                node1.lowerLeft=node;
                return;
            }
            //System.out.println("node ="+node1.key);

        }

    }
    //中序遍历
    public void show(){
        if (root!=null){
            root.middleOrder();
        }
    }
    //节点内部类
    class Node{
         int key;
         Object value;
         Node lowerLeft;
         Node lowerRight;

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public void middleOrder(){
            if(this.lowerLeft!=null){
                this.lowerLeft.middleOrder();
            }
            System.out.println(this.key);

            if (this.lowerRight!=null){
                this.lowerRight.middleOrder();
            }
        }
    }
}
